/*
 *  又是一道关于广度优先搜索的，多源的广度优先搜索解法
 *  腐烂的橘子
 * */

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;
class Solution {
public:

    const int dir[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
    int cnt = 0, ans = 0;
    int dist[10][10];
    int orangesRotting(vector<vector<int>>& grid) {
        queue<pair<int, int>> q;
        memset(dist, -1, sizeof(dist));
        auto m = grid.size(), n = grid[0].size();

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 2) {
                    q.emplace(i, j);
                    dist[i][j] = 0;
                } else if (grid[i][j] == 1) {
                    cnt++;

                }
            }
        }

        while (!q.empty()) {
            auto [r, c] = q.front(); q.pop();

            for (int i = 0; i < 4; ++i) {
                int dx = r + dir[i][0], dy = c + dir[i][1];

                if (dx < 0 || dx >= m || dy < 0 || dy >= n || ~dist[dx][dy] || !grid[dx][dy])
                {
                    continue;
                }

                dist[dx][dy] = dist[r][c] + 1;
                q.emplace(dx, dy);
                if (grid[dx][dy] == 1) {
                    cnt--;
                    ans = dist[dx][dy];
                    //节省时间
                    if (!cnt) {
                        break;
                    }
                }
            }
        }

        return cnt ? -1 : ans;
    }
};